package interview.preparation;

public class Queens {

	 

    static int gridSize;

 

    public static void main(String[] args) {

        gridSize = Integer.valueOf(args[0]);

        int[] array = new int[gridSize];

        placeQueens(array, 0);

    }

 

    private static void placeQueens(int[] array, int row) {

 

        if (row == array.length) {

            printQueens(array);

        } else {

            for (int col = 0; col < array.length; col++) {

                if (checkValid(array, row, col)) {

                    array[row] = col;

                    placeQueens(array, row + 1);

                }

            }

        }

    }

 

    private static void printQueens(int[] array) {

        for (int i = 0; i < array.length; i++) {

            for (int j = 0; j < array.length; j++) {

                if (array[i] == j) {

                    System.out.print("Q ");

                } else {

                    System.out.print("* ");

                }

            }

            System.out.println(" ");

        }

        System.out.println("\n\n\n ");

 

    }

 

    private static boolean checkValid(int[] array, int row1, int col1) {

        for (int row2 = 0; row2 <= row1; row2++) {

            int col2 = array[row2];

            if (col1 == col2) {

                return false;

            }

            int colDiff = Math.abs(col1 - col2);

            int rowDiff = Math.abs(row1 - row2);

            if (colDiff == rowDiff) {

                return false;

            }

        }

        return true;

    }

}